package com.nowcoder.code.lcof;


import com.algorithm.model.TreeNode;

import java.util.*;

public class JZ7 {

    static List<Integer> list = new ArrayList<>();


    public static void main(String[] args) {
        int[] pre = {1,2,4,7,3,5,6,8};
        int[] vin = {4,7,2,1,5,3,8,6};

        TreeNode treeNode = new JZ7().reConstructBinaryTree(pre, vin);

        preOrder(treeNode);
        print();

        list = new ArrayList<>();
        inOrder(treeNode);
        print();
    }

    Map<Integer, Integer> map = new HashMap<>();
    int[] preOrder;

    public TreeNode reConstructBinaryTree(int[] preOrder, int[] vinOrder) {
        this.preOrder = preOrder;
        for (int i = 0; i < vinOrder.length; i++) {
            map.put(vinOrder[i], i);
        }
        return reBuildTree(0, 0, preOrder.length-1);
    }

    public TreeNode reBuildTree(int root, int l, int r) {
        if (l > r) {
            return null;
        }

        int in = map.get(preOrder[root]);
        TreeNode treeNode = new TreeNode(preOrder[root]);

        treeNode.left = reBuildTree(root + 1, l, in - 1);
        treeNode.right = reBuildTree(root + (in - l) + 1, in + 1, r);

        return treeNode;
    }


    public static void ite() {
        TreeNode node = getTree();
        preOrder(node);
        print();

        list = new ArrayList<>();
        inOrder(node);
        print();

        list = new ArrayList<>();
        lastOrder(node);
        print();
    }


    public static TreeNode getTree() {
        TreeNode[] treeNodes = new TreeNode[8];

        for (int i = 0; i < treeNodes.length; i++) {
            treeNodes[i] = new TreeNode(i + 1);
        }

        treeNodes[0].left = treeNodes[1];
        treeNodes[1].left = treeNodes[3];
        treeNodes[3].right = treeNodes[6];

        treeNodes[0].right = treeNodes[2];
        treeNodes[2].left = treeNodes[4];
        treeNodes[2].right = treeNodes[5];

        treeNodes[5].left = treeNodes[7];
        return treeNodes[0];
    }

    public static void print() {
        System.out.println(Arrays.toString(list.toArray()));
    }


    public static void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        list.add(node.val);
        preOrder(node.left);
        preOrder(node.right);
    }

    public static void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        list.add(node.val);
        inOrder(node.right);
    }

    public static void lastOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        lastOrder(node.left);
        lastOrder(node.right);
        list.add(node.val);
    }


}
